#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

int findTargetSumWays(vector<int>& nums, int target);
int backtrack(vector<int>& nums, int target, int &sum, int index);

int findTargetSumWays(vector<int>& nums, int target)
{
    if (nums.size() == 0)
        return 0;
    int sum = 0;
    int index = 0;
    vector<string> flags;
    return backtrack(nums, target, sum, index);
}
map<string, int> memo;
int backtrack(vector<int>& nums, int target, int &sum, int index)
{
    //判断回溯二叉树触底的条件
    if(index == nums.size())
    {
        if (sum == target)
            return 1;
        return 0;
        //0, 1各表示回溯二叉树在这个分支触底结束的时候的分别表示不满足条件，和满足条件 
    }
    string key = to_string(index) + "-" + to_string(sum);

    //查询备忘录
    map<string, int>::iterator it;
    for(it = memo.begin(); it != memo.end(); it++)
    {
        if (it->first == key)
            return it->second;
    }
    sum += nums[index];
    int m = backtrack(nums, target, sum, index + 1);
    sum -= nums[index];

    sum -= nums[index];
    int n = backtrack(nums, target, sum, index + 1);
    sum += nums[index];
    
    memo.insert(pair<string, int>(key, m + n));
    return m + n;
}


int main()
{
    vector<int> nums = {25,29,23,21,45,36,16,35,13,39,44,15,16,14,45,23,50,43,9,15};
    int target = 32;
    cout << findTargetSumWays(nums, target) << endl;
    return 0;
}